package com.yulongtian.interviewWorks.day20221110;

/**
 * https://leetcode.cn/problems/sparse-array-search-lcci/
 *
 * @author yulongTian
 * @create 2022-11-10 16:07
 */
public class Test02 {
    public static void main(String[] args) {
        String[] words = {"at", "", "", "", "ball", "", "", "car", "", "", "dad", "", ""};
        String s = "ta";
        System.out.println(findString(words, s));
    }

    public static int findString(String[] words, String s) {
        int l = 0, r = words.length-1;
        while(r >= l){
            int mid = (l + r) >> 1;
            //当前位置为""，mid前移，就这一个和普通二分不同，其他一模一样
            while(mid > l &&  words[mid].equals("")){
                mid--;
            }
            if(s.compareTo(words[mid]) == 0){
                return mid;
            }
            if(s.compareTo(words[mid]) < 0){
                r = mid - 1;
            }else{
                l = mid + 1;
            }
        }
        return -1;
    }
}
